⟸ pàgina anterior ⟸

Exercici 4 (Tasca 2).

(regular languages, Kleene star, minimization of DFAs)

L’estrella de Kleene d’un llenguatge regular és regular

1. Construïu de forma explícita el DFA mínim per al llenguatge L^*, on

   1. L=\{xay\in\{a,b\}^*\mid |y|=1\}.
   2. L=\{xaby\in\{a,b\}^*\mid |y|=1\}.
   3. L=\{axaby\in\{a,b\}^*\mid |y|=1\}.

   Construïu el mínim DFA que reconeix L. A partir d’aquí, construïu un \lambda-NFA A que reconegui el llenguatge L^*. Fent servir la construcció del conjunt de parts, determinitzeu A i, finalment, minimitzeu el DFA obtingut.

2. Donat un DFA A com a entrada, quin és el cost de construir un DFA per a L(A)^*?